在家摸了将近一个礼拜的鱼(其实整个春夏学期都没有好好训练补题,真 摸得一手好鱼),深感愧疚,回忆起想起去年冬天唯一一场参加的区域赛简直要哭出来,难度啊对手啊都不是跟上半年的比赛完全不是在同一等级。有预感今年依旧发配北京(毕竟有女队关照),决定还是滚回校训练,否则,再有一次近乎于爆零的体验怕是真的能当场哭出来,虽然不打铁是不可能的,但是,要优雅地拿铁!最近会把上半年做的题和最近的训练汇总一下,加油啦袁干干!
A - Quoit Design(HDU 1007)
因为在家所以一直都没开电脑(在家休息怎么能训练呢!),这场比赛最后一天文文拉我做的(心不甘情不愿地开电脑),但还是为自己的懈怠羞愧一秒….当时因为做的人少我也就没开这题,今天补题一看,噫,这道题我写过的,不就是个平面最近点对吗…这个故事告诉我们,打比赛至少要把每道题都看一遍!
分治的思想,最近的点肯定是位置相近的点(废话),那么先按照x和y排序,我们可以把这么多点分为左部分和右部分,最近的两点肯定出现在左部分内部或右部分内部或者一点属于左部分,一点属于右部分。左右部分内部的点的距离可以通过递归来求得,递归的终点是左右端点相邻。而一点属于左部分,另一点属于右部分的情况,则是根据刚才求得的两个内部的最短距离d确定的。我们筛选出离中间点距离不超过d的点(因为只有横向距离不超过d才有可能成为最近点),这里是个优化,本来应该两两筛选,但是这样效率低下,用中间点来筛,虽然造成了候选点更多,但保证了候选点不漏,且在O(n)的时间就能筛完。将候选点按照y排序,使点两两比较并更新d,这是另一个优化,因为之前按照x排序,break几率不大,以y排序,当纵距离>d时马上换下一个候选点,加快更新速度。
下面是代码:
1 |
|
B - 前m大的数 (HDU 1280)
给3000个数,求两两相加最大的m个数。
直接暴力相加然后排序输出。
1 |
|
C - 今年暑假不AC (HDU 2037)
给100个节目,给出它们的开始时间和结束时间,看的时候不能换台,求最多能看多少个节目(端点可以重合)。
简单的贪心,每一次都选取结束时间小的那个节目就好,这样才会对之后的收看情况影响最低。
1 |
|
D - 折线分割平面 (HDU 2050)
又到了干干最不拿手的找规律时间啦,我我我我选择放弃,让队友去找(突然丢锅)。直接贴代码。
1 |
|
E - Can you find it? (HDU 2141)
给A B C 三个数组,每个长度在500,再给1000个X,问X可不可能由A B C中各一个元素加和而成。
有点折半枚举的意思。三重暴力枚举时间不够,所以先由AB两两组合,将C数组排序,在C数组中二分寻找(X-(a+b))。
这道题给的内存有点小,刚开始我用set来记录a+b,然后就MLE了,换数组就过了,看来维持set是需要很大的开销的。
1 |
|
F - Hello World! (HDU 3257)
给你一个16进制的矩阵,让输出图案。映射关系也没说明,让自己找。
仔细观察就能发现 将16进制换为2进制,当前位是1的话就输出‘#’,为0的话输出‘ ’,算是个简单的小模拟吧(然后PE了2发,真是辣鸡QAQ)。
1 |
|
G - Exam (HDU 4473)
定义f(n)为 $(a*b)|n$ 的这样ab的对数,给定n,求f(1)+f(2)+…+f(n)
看到题第一反应:束手无策,不知所措…
要注意转化!转化!
$(ab)|n$ 不就是 $ab*c=n$ ! 求ab对的数量,不就是求abc对的数量!
题目中的f(1)+f(2)+…f(n)不就是求$a b c \le n$的abc对的数量!
那么我们假设 a<=b<=c 则可能关系有以下四种:
1 | a=b=c |
设以上分别有A B C D种,则最后答案就有A+3(B+C)+6D 种
以下是代码:
1 |
|
H - Digit-Sum (HDU 5710)
16年女生赛的题,当时的第5/6题的样子?
给定S(n)为n的数位和,给定a和b,让你求出满足 aS(n)=bS(2n)的n,如果不存在则输出0。
首先来看一下S(n)和S(2n)的关系。我们可以发现,对于0~4,2S(n)=S(2n),但是对于5~9,2S(n)=S(2n)-9.假设n中有x位大于4的数位,则S(2n)=2*S(n)-9x (式1)。
2n的数位和只会损失不会增加,所以2S(n)>=S(2n)。如果a>2b时,那么这样的n不可能存在。如果a==2*b,那么直接输出只有0~4的正数即可。
由式1得,x/S(n) = (2b-a)/9b (式2)
要想n最小,那么肯定x和S(n)尽量小,最小就是(2b-a)/gcd(2b-a,9b)和(9b)/gcd(2b-a,9b)。 显然如果5*x>S(n)的话,这个n就不存在。有了最小的x和S(n),我们就可以构造出最小的n了。构造思想是,尽量将x位大于4的值往后放,最好放9将S(n)用尽,如果用不完,则前面小于5的尽量放4,尽量缩短长度来减小n。
1 |
|
总结:学弟们可真强啊, 写题解可真累啊,滚去吃饭,再见!